The medial axis (or “topological skeleton”) of an object, first described by Blum [1], can be defined as the set of points within the object that are equidistant from two or more closest points along the object's boundary. An accurate skeleton is a highly efficient way to represent the topology of 2D or 3D objects in a compact way [2][3] and has been widely used in various fields such as image processing and analysis, video graphics, character reconstruction, recognition and matching [4][5].
Extraction of the medial axis or medial axis transform (MAT) for 2D/3D object has typically fallen in one of the following three categories [6]: 1) boundary removal, 2) distance map suppression, or 3) geometric methods.
Boundary removal, also known as morphological thinning [7][8][9], is an iterative process of removing the boundary of an object, starting from the outside and moving toward the center. Different thinning algorithms have been described [10], but most of these are an approximation of the grassfire process [11] that work like peeling an onion to reach its core. All pixels/voxels are removed except those whose removal affects the topology of an object [12][13]. However, there are several drawbacks to this approach. The processing time increases rapidly with the size of the object because each pixel/voxel must be evaluated independently [14]; and both the accuracy of the estimated skeleton and the processing time depend critically on how many neighboring pixels (e.g., 4 vs. 8) or voxels (6 vs. 24) are considered during the thinning process [1][15]. Generally speaking, accounting for more neighboring pixels/voxels, yields a more accurate representation of the medial axis, but including more neighbors means that processing time will also increase. Also different thinning algorithms produce different skeletons when applied to the same image [10]. And finally, because it is an iterative process, an appropriate stopping criteria needs to be defined a priori, which may not be trivial.
On the other hand, distance transforms (DT) can be used to extract the medial axis by creating a distance map of an object [16][17]. The distance map is created by assigning each pixel of an object a value that is determined by its distance to the closest boundary [18], based on a predetermined distance calculation method (e.g., Euclidean [19], chessboard [20], city block [19] etc.). After creating the distance map, the medial axis is then extracted by suppressing pixels with a non-maximum distance [15], since (by definition) pixels in the middle have the largest distance from the boundary. This process is also known as ridge detection [21], and is done using local/global adaptive thresholding approaches or gradient-based methods. This is a relatively fast and simple process compared to boundary removal. However, the main drawback is that the resulting medial axis may not be one-pixel thin, or that holes/discontinuities can sometimes appear in the resulting skeleton.
Finally, medial axes can be extracted using geometry-based algorithms such as Voronoi diagrams [22][23][24][25], where the original object is first divided into polygons and the centers of those polygons are subsequently determined using maximal disks. Skeletonization based on Voronoi diagrams is very robust, and often produce skeleton having one-pixel thin, continuous, and maintain the topology description. The Voronoi method also has the advantage of being computationally efficient, and is therefore faster than boundary removal or distance transform methods for large and/or complex objects [26]. The primary drawback of this approach is that the extracted skeleton may contain additional/redundant information due to the presence of noise; however, this can be removed using various pruning methods [27][28][29]. The main pipeline or workflow for all the three categories are shown in FIG. 1.
According to the definition of Voronoi diagram, the space S between two points p1 and p2 is equally divided with the help of the bisector E, that passes perpendicularly at the center of the line segment joining points p1 and p2 [30][31], as shown in FIG. 2(a). Similarly, space S having many points P (also called sites) can be equally divided into Voronoi regions (also called Voronoi cells) among these points P. Each Voronoi cell, which is a convex polygon, will have only one site within it and any points on its boundaries, called Voronoi edges, are equidistant from exactly two sites. Intersection of three Voronoi edges will give rise to a Voronoi vertex, which is equidistant from exactly three sites. Thus, a Voronoi diagram is the final result of partitioning an object into Voronoi cells.
Different algorithm can be used in order to calculate the Voronoi diagram of n sites. These algorithms include a lower bound [32][33], incremental construction [34] whose efficient implementation was done by Ohya [35] and Sugihara [36], divide & conquer [37] and a well-known sweep algorithm [38].
Assuming that there is only one object present in the image whose medial axis is being extracted, all points of the medial axis are centered with respect to the boundaries of that object. Therefore, before the Voronoi diagram can be generated, the object boundaries must be identified. Different edge detectors (e.g. sobel or canny or any other edge operator, details can be found in [39]) can be used in order to detect the boundary of an object within the image. Then, once the boundary of the object has been identified, the space can be divided into Voronoi cells (as described above).
The raw Voronoi skeleton of an object contains branches that are clearly outside of the object's boundaries, but still within the image. These branches/segments do not have any significant value, as these are segments of unbounded polygons (as described above). Therefore, initial cleaning has to be done to remove all of the segments that lie outside the object's boundaries.
Due to the presence of noise in the boundary information, the resulting Voronoi diagram of an object may not be considered a medial axis if it contains spurious branches. Therefore, pruning—i.e., the process of determining whether a specific branch of the skeleton is redundant or not, and if so, removing the redundant segment—may be necessary to remove these spurious branches and to extract the true medial axis. The pruning process implemented in this paper compares the Euclidean distance between two sites with their contour distance along the boundary, as explained below [22].
Each Voronoi edge, a branch of the raw skeleton, is equidistant from exactly two sites (p1 & p3) as mentioned earlier. These two sites can provide information about the Euclidean distance (distE) and contour distance (distc) between them. The Euclidean distance between two points (p1 & p2) having spatial coordinates (x1,y1) and (x2,y2) respectively, is calculated using following equation.distE=√{square root over ((x1−x2)2+(y1−y2)2)}  (2.1)
The Euclidean distance serves as the diameter for the maximal disk Dc, which can fit between those two sites (pi & pj) having these sites on its circumference. The area (DA) and the circumference (Dc) of this maximal disk can be calculated using following equations:
                              D          A                =                  T          ·                                    (                                                dist                  E                                2                            )                        2                                              (        2.2        )                                          D          C                =                  2          ⁢                                          ⁢                      T            ·                          (                                                dist                  E                                2                            )                                                          (        2.3        )            where T is a control parameter with values less than, equal to, or greater than π (e.g., π/3, π/2, 2π/3, π, 3π/2, 2π, 3π, etc.). The effects of varying the magnitude of the control parameter are demonstrated in experimental results found herein below.
The contour distance is the distance between two points while moving along the boundary of an object as shown in FIG. 3. There are two pathways to calculate the contour distance between two points while moving along the boundary. The minimum of the two contour distances is selected. Both the distances (distE & distc) are shown in FIG. 3.distc=min(distc1,distc2)  (2.4)
The Voronoi edge is considered to be spurious if the contour distance (distc) is less than the circumference DC of the maximal disk with a diameter equal to the Euclidean distance, such that:
                              Voronoi          ⁢                                          ⁢          edge                =                  {                                                    spurious                                                                                  dist                    c                                    <                                      D                    C                                                                                                                        not                  ⁢                                                                          ⁢                  spurious                                                            otherwise                                              }                                    (        2.5        )            
FIG. 3 demonstrates how an edge is decided spurious or not. Edgex, edgey and edgez are equidistant from sites (p1 & p2), (p3 & p4) and (p5 & p6, respectively. For edgex and edgey, the minimum of their respective contour distance distc is larger than then circumference of the circle having diameter equal to their respective sites' Euclidean distance. Therefore, these edges are not considered to be spurious and are not eliminated from the final accurate skeleton. However, the minimum contour distance for edgez is less than the circumference of the circle containing (p5 & p6), so this edge is considered spurious and is excluded from the final skeleton. After checking all the Voronoi edges, the refined skeleton is created as shown in FIG. 4.
In accordance with the forgoing, the procedure for medial axis extraction of a 2D image is briefly summarized below, with reference to the block diagram shown in FIG. 5.                Step 1: Generate binary image.        Step 2: Boundary detection.        Step 3: Raw skeleton using Voronoi diagram algorithm.        Step 4: Initial cleaning process.        Step 5: Pruning of raw skeleton.                    5.1: Pick Voronoi edge.            5.2: Find its corresponding sites.            5.3: Calculate the distc and Dc.            5.4: Check for spurious edge using equation 5.            5.5: Refine the raw skeleton.                        Step 6: Continue step 4 for all edges and generate medial axis.        
While the forgoing process is useful for deriving the medial axis for a 2D image, it is not directly applicable to determine the medial axis for a 3D object. It is in relation to this problem that Applicant has developed a unique process that builds on the forgoing principles to find the medial axis of a 3D object.